"""
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的.

example
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
"""

def imporved_solution(coins,amount):
    """
    use memo to keep the calculated value
    """
    memo = {}
    def recursive(amount):
        res = float("inf")
        if amount == 0:
            return 0
        if amount < 0:
            return -1
        if amount in memo:
            return memo[amount]
        for coin in coins:
            if recursive(amount-coin)==-1:
                continue
            res = min(res,recursive(amount-coin)+1)
        memo[amount] = res
        return memo[amount]
    return recursive(amount)


if __name__ =="__main__":
    coins = [1, 2, 5]
    amount = 11
    print(imporved_solution(coins,amount))